package main

import "fmt"

/*
  丑数 II
给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。

示例 1：
输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
 */

/*

由于后面的丑数都是在2 3 5的基础上的
定义dp保存数据  初始时dp[0] = 1表示第一个丑数

定义三个指针p1, p2, p3，表示下一个丑数是当前指针指向的丑数乘以对应的质因数。初始时，三个指针的值都是1
dp[i] = min(dp[p1] * 2, dp[p2] * 3, dp[p3] * 5)

然后分别比较dp[i] 与 dp[p2]*2, dp[p3]*3, dp[p5]*5是否相等
*/

func nthUglyNumber(n int) int {
	dp := make([]int, n+1)
	dp[1] = 1
	p2, p3, p5 := 1, 1, 1
	for i := 2; i <= n; i++ {
		x2, x3, x5 := dp[p2]*2, dp[p3]*3, dp[p5]*5
		dp[i] = minNum(minNum(x2, x3), x5)
		if dp[i] == x2 {
			p2++
		}
		if dp[i] == x3 {
			p3++
		}
		if dp[i] == x5 {
			p5++
		}
	}
	return dp[n]
}

func minNum(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func main() {
	fmt.Println(nthUglyNumber(5))
}
